package baseclass.j_dp.dp.fullBag;

import java.util.Arrays;

/**
 * 有n种重量和价值分别为wi，vi的物品。从这些物品中挑选总重量不超过m的物品，
 * 求出挑选物品价值总和的最大值。在这里，每种物品可以挑选任意多件.
 * <p>
 * <p>
 * 分析：
 * 从第0号商品开始，背包开始装0件一直到装满。
 * 从第1号商品开始，背包开始装0件一直到装满。
 * ….
 * 从第n-1号商品开始，背包开始装0件一直到装满。
 * 记录以上每个过程的最值。
 *
 * @date 2020/3/3 16:59
 */
public class Code01_FullBag {
    public static int process1(int[] W, int[] V, int bag, int index) {
        if(bag == 0) return 0;
        if (index >= W.length) return 0;
        //对于当前物品，要0件到要count件，然后考虑下一件物品
        int res = 0;
        for (int count = 0; count * W[index] <= bag; count++) {
            int temp = count * V[index] +
                    process1(W, V, bag - count * W[index], index + 1);
            res = Math.max(temp, res);
        }
        return res;
    }

    /**
     * 如 W = [1,2,x,...] V = [1,2,x,...]
     * 前两件商品要2件1和0件2 和要1件2和0件1  对于3来说都是 受益是2，重量是2.
     * 是重复子问题
     */
    public static int process2(int[] W, int[] V, int bag) {
        int[][] memo = new int[W.length][bag + 1];
        for (int[] ints : memo) {
            Arrays.fill(ints, -1);
        }
        return doProcess2(W, V, bag, 0, memo);
    }

    private static int doProcess2(int[] W, int[] V, int bag, int index, int[][] memo) {
        if(bag == 0) return 0;
        if (index >= W.length) return 0;
        //对于当前物品，要0件到要count件，然后考虑下一件物品
        if (memo[index][bag] != -1) return memo[index][bag];
        int res = 0;
        for (int count = 0; count * W[index] <= bag; count++) {
            int temp = count * V[index] +
                    doProcess2(W, V, bag - count * W[index], index + 1, memo);
            res = Math.max(temp, res);
        }
        return memo[index][bag] = res;
    }


    /**
     * 方式3：完全背包DP
     * dp[i][j]表示装下前i+1个商品后背包质量为j的情况下，形成的最大利润
     * 状态转移方程
     * dp[i][j] =
     * max(dp[i-1][j],V[i]+dp[i-1][j-W[i]],2V[i]+dp[i-1][j-2W[i]],……,
     * KV[i]+dp[i-1][j-KW[i]]))
     *
     * 其中j-KW[i] >= 0 , j-(K+1)W[i] < 0
     * <p>
     * 代码如下：
     * 时间复杂度O(M*N),M是商品数，N是背包质量。过高，转为0-1背包问题。
     */
    private static int dp1(int[] W, int[] V, int bag) {
        int number = W.length - 1;
        int[][] dp = new int[number + 1][bag + 1];
        for (int j = 0; j <= bag; j++) {
            //当前容量为j，只能装第0号商品，无限装
            dp[0][j] = (j / W[0]) * V[0];
        }
        //从1号商品开始决策
        for (int i = 1; i <= number; i++) {
            //对背包质量从0到bag开始决策
            for (int j = 0; j <= bag; j++) {
                //当前商品不装
                dp[i][j] = dp[i - 1][j];
                //如果背包容量够了，一直装当前商品
                for (int count = 1; count * W[i] <= j; count++) {
                    dp[i][j] = Math.max(dp[i][j],
                            count * V[i] + dp[i - 1][j - count * W[i]]);
                }
            }
        }
        return dp[number][bag];
    }

    /**
     * 方式4：转为0-1背包，转移方程。分析见笔记
     * <p>
     * dp[i][j] = Math.max(dp[i-1][j],V[i] + dp[i][j-W[i])
     * 注意0-1背包的DP方程如下 ：
     * dp[i][j] = Math.max(dp[i-1][j],V[i] + dp[i-1][j-W[i])
     */
    private static int dp2(int[] W, int[] V, int bag) {
        int number = W.length - 1;
        int[][] dp = new int[number + 1][bag + 1];
        for (int j = 0; j <= bag; j++) {
            //当前容量为j，只能装第0号商品，无限装
            dp[0][j] = j / W[0] * V[0];
        }
        //从1号商品开始决策
        for (int i = 1; i <= number; i++) {
            //对背包质量从0到bag开始决策
            for (int j = 0; j <= bag; j++) {
                //当前商品不装
                dp[i][j] = dp[i - 1][j];
                if (j - W[i] >= 0)
                    dp[i][j] = Math.max(dp[i][j], V[i] + dp[i][j - W[i]]);
            }
        }
        return dp[number][bag];
    }


    private static int dp3(int[] W, int[] V, int bag) {
        int[] dp = new int[bag + 1];
        for (int j = 0; j <= bag; j++) {
            dp[j] = j / W[0] * V[0];
        }

        for (int i = 1; i < W.length; i++) {
            //这里要正序遍历，当前物品i可以一直拿
            for (int j = W[i]; j <= bag; j++) {
                dp[j] = Math.max(dp[j], V[i] + dp[j - W[i]]);
            }
        }
        return dp[bag];
    }

    public static void main(String[] args) {
        int[]W = {1,2,3,2,6};
        int[]V = {2,1,5,2,100};
        int bag = 10;
        System.out.println(process1(W,V,bag,0));
        System.out.println(process2(W,V,bag));
        System.out.println(dp1(W,V,bag));
        System.out.println(dp2(W,V,bag));
        System.out.println(dp3(W,V,bag));
    }

}
